package com.liang.leetcode.dp;

import java.util.Arrays;

/**
 * 62.不同路径
 */
public class Dp04_UniquePaths {
    public static void main(String[] args) {
        int m = 3;
        int n = 7;
        System.out.println(uniquePaths3(m, n));
    }

    /**
     * 解法1：DFS 深度优先搜素（会超时）
     * 机器人每次只能向下或者向右移动一步，将机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点，
     * 从而转化为求二叉树叶子节点的个数
     */
    public static int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }

    /**
     * 用 DFS 计算从起点到终点的路径数
     * @param i 当前位置的行坐标
     * @param j 当前位置的列坐标
     * @param m 网格的总行数
     * @param n 网格的总列数
     * @return 从当前位置 (i, j) 到终点 (m, n) 的路径数
     */
    public static int dfs(int i, int j, int m, int n) {
        // 越界了
        if (i > m || j > n) {
            return 0;
        }
        // 找到一种方法，相当于找到了叶子节点
        if (i == m && j == n) {
            return 1;
        }
        // 递归调用：探索下一步向下和向右的路径数之和
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }

    /**
     * 解法2：动态规划
     * dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
     * dp[i][j] 表示从 (0,0) 出发，到 (i, j) 有 dp[i][j] 条不同的路径。
     * 每次只能向下或向右移动，所以到达每个点的路径数等于到达其上方的点和左侧的点的路径数之和
     */
    public static int uniquePaths2(int m, int n) {
        int[][] dp = new int[m][n];
        // dp[i][0]一定为1，因为只有向下一条路可以走
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        // dp[0][j]一定为1，因为只有向右一条路可以走
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        // 遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 解法 2 优化，状态压缩
     * 用 dp[j] 保留当前列的路径数，而 dp[j - 1] 保留左侧格子的路径数
     */
    public static int uniquePaths3(int m, int n) {
        int[] dp = new int[n];
        // 都初始化为1，想象成二维数组的第一行数据
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

}
